package org.leetcode.middle.leetcode131;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Solution
{

    List<List<String>> res = new ArrayList<>();

    List<String> item = new ArrayList<>();

    Deque<String> deque = new LinkedList<>();
    public List<List<String>> partition(String s) {

        backtracking(s,0);

        return res;
    }

    private void backtracking2(String s ,int startIndex){
        if (startIndex == s.length()){
            res.add(new ArrayList<>(item));
            return;
        }

        for (int i = startIndex; i < s.length(); i++) {
            if (isPalindrome(s,startIndex,i)){

                item.add(s.substring(startIndex,i+1));

                backtracking(s,i+1);

                item.remove(item.size()-1);
            }

        }
    }

    public void backtracking(String s ,int startIndex)
    {
        if (startIndex>s.length()-1)
        {
            res.add(new ArrayList<>(deque));
            return;
        }


        for (int i = startIndex; i <s.length(); i++) {

            if (isPalindrome(s,startIndex,i))
            {
                String str = s.substring(startIndex, i + 1);
                deque.addLast(str);
            }else {
                //continue语句确保进入backtracking之前，deque中存放的都是回文
                continue;
            }

            backtracking(s,i+1);

            //回溯
            deque.removeLast();

        }
    }


    //判断是否是回文字符串
    private boolean isPalindrome(String s, int startIndex, int end)
    {

        for (int i = startIndex,j=end; i < j; i++,j--)
        {
            if (s.charAt(i)!=s.charAt(j))
            {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        String str = "zhang";

       // System.out.println(str.substring(0,1));


        for (int i = 0; i < 10; i++) {
            if (i<5)
            {
                System.out.println(i);
            }else {
                continue;
            }

            System.out.println("zhang");
        }
    }

}
